package com.computer.fundamentals.algorithm;


import java.util.Stack;

/**
 * 单调栈的应用：区间最小值和区间和的乘积的最大值
 * ---------------------------------------------------------------------------------------------------------
 *  给定一个数组，要求选出一个区间, 使得该区间是所有区间中经过如下计算的值最大的一个：区间中的最小数 * 区间所有数的和。
 *  数组中的元素都是非负数。
 *
 *  输入两行，第一行n表示数组长度，第二行为数组序列。输出最大值。
 *  ---------------------------------------------------------------------------------------------------------
 */
public class IntervalMinimumTimesTheIntervalAndMaximumValues {

    /**
     * 解决方案如下
     *  方案一：枚举法  O(2^N)
     *      1. 利用回溯法将所有可能的区间罗列出来
     *      2. 计算每个区间的最小值与区间和的乘积
     *      3. 逐个比较，得出最大值
     *
     *  方案二：优化暴力求解【贪心】 O(N^2)
     *      上述枚举法会加入很多无效区间，本题隐含了一个假定，即最小值确定的情况下区间越长越好，根据这种贪心策略可以再次优化
     *      1. 将数组下的每一个元素都作为最小值
     *      2. 探测比该值大的左右边界，即向左向右探测到小于当前元素的值的时候就停止遍历
     *      3. 计算区间和，并得出最大值
     *
     *  方案三：单调栈【贪心优化】 O(N)
     *      方案二的局限性在于探测这一过程消耗了很多时间，引入单调栈结构可以优化这一过程
     */
    public static int solution(int[] nums) {
        int n = nums.length;
        int[] prefix = new int[n+1];
        for (int i = 1;i <= n;i++) {
            prefix[i] = prefix[i-1] + nums[i-1];
        }
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0;i < n;i++) {
            // 当前位置i表示右边界，栈顶元素为最小值，栈顶左侧元素为左边界
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                int peek = nums[stack.peek()];
                stack.pop();
                int left = stack.isEmpty() ? -1 : stack.pop(); // 栈为空证明当前右边界较小，因此左边界就为0
                int right = i;
                res = Math.max(res, peek * (prefix[right] - prefix[left+1]));
            }
            stack.push(i);
        }
        // 因为第一次遍历时栈内可能有一部分递增的值没有进行计算，而这些值的右边界均为n-1
        while (!stack.isEmpty()) {
            int peek = nums[stack.peek()];
            stack.pop();
            int left = stack.isEmpty() ? -1 : stack.pop();
            int right = n;
            res = Math.max(res, peek * (prefix[right] - prefix[left+1]));
        }
        return res;
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        System.out.println("------------测试------------");
        System.out.println(solution(new int[] {6, 2, 1}));

    }
}
